#############################
##						 ##
##   WeightedAStar Search Algorithm   ##
##						 ##
#############################

# This is an implementation of the SearchAlgorithm interface for the following
# search algorithms:
# - A*
# - IterativeDeepeningAStar
#
# The IterativeDeepeningAStar variant allows you to search with A* using layers
# of depth in the graph, with each search increasing the maximum depth.

from algorithm import Heuristic, SearchAlgorithm
from graph import GraphSearch
from utils import *

class WeightedAStar (SearchAlgorithm):

	def __init__(self, max_depth=infinity):
		self.max_depth = max_depth

	def find(self, problem_state, heuristic, w):
		def evaluator(node):
			x = node.path_cost
			y = heuristic.evaluate(node.state)
			a = (1-w) * x + w * y;
			b = x+y;
			print "should return ", b, "but returns ", a, "w = ", w, "x =", x, "y=", y
			return a
	
		# This is a generator for the PriorityQueue we need.
		def queue_generator():
			return PriorityQueue(evaluator)

		# Use a graph search with a minimum priority queue to conduct the search.
		search = GraphSearch(queue_generator, self.max_depth)
		return search.find(problem_state)